package substr

// All
//	(a,n_0),(n_0,n_1),...,(n_(m-1),n_m),(n_m,b)
// are replaced by
//	(a, b).
// The operation is inplace and returns itself for chaining.
func (s *S) MergeConsecutive() *S {
	ln := len(s.Subs)
	if ln == 0 || ln == 1 {
		return s
	}

	w, r, rp, a := 0, 0, 0, 0 // 0 <= w <= r < ln and r' < ln - 1
	for ; r < ln; r++ {
		a = s.Subs[r][0]

		//scan while there right(A_r) = n and left(A_(r+1)) = n
		for rp = r; rp < ln-1; rp++ {
			if s.Subs[rp][1] != s.Subs[rp+1][0] {
				r = rp - 1
				break
			}
		}

		//if r = r' then right(A_r) /= left(A_(r+1))
		if r == rp {
			//just move A_r to A_w
			s.Subs[w] = s.Subs[r]
		} else {
			//merge start of run with end of run
			s.Subs[w] = []int{a, s.Subs[rp][1]}
			r = rp
		}
		w++
	}

	for i := w; i < ln; i++ {
		s.Subs[i] = nil
	}
	s.Subs = s.Subs[:w]
	return s
}

// Replace matched substrings with their opposites.
// There may be two more substrings or one less substring after inversion.
// The operation is inplace and returns itself for chaining.
func (s *S) Invert() *S {
	ln, sln := len(s.Subs), len(s.Super)
	//the opposite of no matches is a complete match
	if ln == 0 {
		s.Push(0, -1)
		return s
	}
	//we say a side is open if it includes an endpoint of the string
	lopen, ropen := s.Subs[0][0] == 0, s.Subs[ln-1][1] == sln
	//the opposite of a complete match is no match
	if ln == 1 && lopen && ropen {
		s.Subs[0] = nil
		s.Subs = s.Subs[:0]
		return s
	}
	new := make([][]int, ln+1) //an inversion may be longer by one
	w := 0
	//we have to treat the end points specially, using the implicit bounds
	if !lopen {
		new[0] = []int{0, s.Subs[0][0]}
		w = 1
	}
	for i := 0; i < ln-1; i++ {
		new[w] = []int{s.Subs[i][1], s.Subs[i+1][0]}
		w++
	}
	if !ropen {
		new[w] = []int{s.Subs[ln-1][1], sln}
		w++
	}
	s.Subs = new[:w]
	return s
}
